Proposition - Die Anzahl signierter Teilmengen einer m-elementigen Menge ist 3^m

• Involvierte Definitionen:
  • Signierte Charakteristische Funktion
  • Signierte Teilmenge
• Veranstaltung: AlMa
• Referenz: AlMa

⠀

Proposition: Die Anzahl signierter Teilmengen einer -elementigen Menge ist

Die Anzahl signierter Teilmengen einer -elementigen Menge ist .

Beweis

Es ist zu zeigen, dass eine Menge genau signierte Teilmengen hat.

Die Menge der möglichen Tupel erhalten wir, in dem wir zählen, wie viele mögliche Funktionsvorschriften gibt.

Da jedes Urbild nur einem einzigen Bild zugeordnet werden kann, gilt:

• entweder
• oder
• oder .

In anderen Worten:

• jede signierte Teilmenge definiert eindeutig eine signierte charakteristische Funktion und
• jede signierte charakteristische Funktion definiert eindeutig eine signierte Teilmenge

Aus einem früheren Beweis wissen wir bereits, dass die Anzahl aller Funktionsvorschriften einer Funktion beträgt.

In unserem Fall gilt: und .

Das heißt, hat genau signierte Teilmengen